/*
The code is used to select the ith smallest elements of an array.
The pseudo code can be found in page 216
*/

#include<iostream>
using namespace std;

const int minInt = -2147483648;

void exchange(int *A, int a, int b)
{
	int tmp = A[a];
	A[a] = A[b];
	A[b] = tmp; 
}

int partition(int *A, int p, int r)
{
	int pivot = A[r];
	int i;
	int k=p-1;
	for(i=p;i<r;i++)
	{
		if(A[i]<pivot)
		{
			k++;
			exchange(A,k,i);		
		}
	}
	k++;
	exchange(A,k,r);
	return k;
}

int random_select(int *A, int p, int r, int i)
{
	if(p==r)
	{
		return A[p];
	}
	int q = partition(A,p,r);

	int k = q-p+1;	// the number of elements in A[p...q];
	if(k==i)
		return A[k];
	if(i<k)
		return random_select(A,p,q-1,i);	// ith smallest element in A[p...q-1]
	else
		return random_select(A,q+1,r,i-k);	// ith smallest element in A[q+1...r]. i must minus k because in the next iteration, the array begins from q+1. We already know the A[i] is > all elements in A[p...q]
}

int main()
{
	int A[9] = {minInt, 2,8,7,1,3,5,6,9};
	int res = random_select(A,1,8,4);
	cout << res << endl;
	return 0;
}
